package com.cat.slidingWindow;

import java.util.HashMap;

/**
 * @author cat
 * @description https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
 * @create 2025/7/29 14:58
 * @since JDK17
 */

public class Solution10 {
    // 解法一 : 前缀和 + 加哈希表将其转换为两数之和

    static int N = ((int) (1e5 + 10));
    static long[] prefix = new long[N];
    static HashMap<Long, Integer> map = new HashMap<>();
    public int minOperations01(int[] nums, int x) {
        map.clear();
        int ans = 0, n = nums.length;
        // 做前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
            map.put(prefix[i + 1], i + 1);
        }
        long target = prefix[n] - x;    // 总和
        // 现在问题已经转换成了两数之和
        for (int i = 1; i <= n; i++) {  //
            if (map.containsKey(prefix[i] - target)) {
                ans = Math.max(ans, i - map.get(prefix[i] - target));
            }
        }
        return n - ans;
    }

    // 解法二 : 滑动窗口

    public int minOperations(int[] nums, int x) {
        int ans = Integer.MAX_VALUE, n = nums.length, sum = 0;
        for (int num : nums) sum += num;
        int target = sum - x;
        if (target == 0) {
            return n;
        }
        sum = 0;
        for (int l = 0, r = 0; r < n; r++) {
            sum += nums[r]; //
            while (l < r && sum > target) {
                sum -= nums[l++];
            }
            if (sum == target) {    // 求答案了
                ans = Math.min(ans, n - (r - l + 1));
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
